import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;

public class num347 {
    //给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
    public int[] topKFrequent(int[] nums, int k) {
        int[] ret = new int[k];
        Map<Integer,Integer> map = new HashMap<>();
        for(int i : nums){
            if(map.containsKey(i)){
                int time = map.get(i);
                map.put(i,time + 1);
            }else{
                map.put(i,1);
            }
        }
        //遍历哈希表，找到出现频率最大的k个数
        Queue<Freq> queue = new PriorityQueue<>();
        for(Map.Entry<Integer,Integer> entry : map.entrySet()){
            if(queue.size() < k){
                queue.offer(new Freq(entry.getKey(),entry.getValue()));
            }else{
                int v = queue.peek().val;
                if(entry.getValue() > v){
                    queue.poll();
                    queue.offer(new Freq(entry.getKey(),entry.getValue()));
                }
            }
        }
        //把队列中的数添加到数组中
        int i = 0;
        while (!queue.isEmpty()){
            ret[i++] = queue.poll().key;
        }
        return ret;
    }
}
class Freq implements Comparable<Freq> {
    int key;//存放每个不一样的数
    int val;//存放每个数出现的次数
    public Freq(int key,int val) {
        this.key = key;
        this.val = val;
    }
    @Override
    public int compareTo(Freq o) {
        return this.val - o.val;
    }
}